package algorithm.morris;

public class MorrisTraversal {

    //用morris对二叉树进行遍历的空间复杂度O（1）；
    //二叉树的递归套路会回到一个节点三次，
    //***如果一个节点有左子树，morris遍历会来到该节点两次，即访问完左子树后会返回回去

    //如果解题需要知道左右两颗子树的完整信息才能得到以当前节点为头的信息只能用二叉树的递归套路
    //在只需要知道左节点信息就可以求解的题目来说最优解法是morris遍历

    //过程：
    //如果当前节点没有左子树，当前节点来到右子树；
    //如果当前节点有左子树，
    //      如果左子树的最右节点a的右节点为null，表示第一次来到当前节点,
    //         需要将a的右节点指向当前节点，当前节点来到左节点。
    //      如果左子树的最右节点a的右节点指向当前节点，表示第二次来到当前节点，
    //         需要将a的右节点恢复为null，当前节点来到右节点。

    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

    public static void morris(Node head){
        if(head == null)
            return;
        Node cur = head;
        Node mostRight;
        while(cur != null){
            System.out.println(cur);
            if(cur.left == null){
                cur = cur.right;
            }else{
                mostRight = cur.left;
                while(mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                }else {
                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }
    }


    //如果当前节点没有左子树，则打印当前节点
    //如果当前节点有左子树吗，则在第一次到当前节点时打印
    public static void morrisPre(Node head){
        if(head == null)
            return;
        Node cur = head;
        Node mostRight;
        while(cur != null){
            if(cur.left == null){
                System.out.println(cur);//如果当前节点没有左子树，则打印当前节点
                cur = cur.right;
            }else{
                mostRight = cur.left;
                while(mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if(mostRight.right == null){
                    System.out.println(cur);//如果当前节点有左子树吗，则在第一次到当前节点时打印
                    mostRight.right = cur;
                    cur = cur.left;
                }else {
                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }
    }//4213657

    //如果当前节点没有左子树，则打印当前节点
    //如果当前节点有左子树，则在第二次到达当前节点时打印
    //（意味着会先遍历左子树，等遍历完左子树第二次到达当前节点，即回到当前节点时在打印当前节点，完成中序遍历）
    public static void morrisIn(Node head){
        if(head == null)
            return;
        Node cur = head;
        Node mostRight;
        while(cur != null){
            if(cur.left == null){
                System.out.println(cur);//如果当前节点没有左子树，则打印当前节点
                cur = cur.right;
            }else{
                mostRight = cur.left;
                while(mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                }else {
                    System.out.println(cur);//如果当前节点有左子树，则在第二次到达当前节点时打印
                    mostRight.right = null;
                    cur = cur.right;
                }
            }
        }
    }//1234567

    //只有当第二次返回到当前节点的时候才会进行处理，逆序打印当前节点左子树的右边界
    public static void morrisPos(Node head){
        Node cur = head;
        Node mostRight;
        while(cur != null){
            if(cur.left == null){
                cur = cur.right;
            }else {
                mostRight = cur.left;
                while(mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                }else {
                    //第二次来到当前节点
                    mostRight.right = null;
                    printRightEdge(cur.left);//将当前节点左子树的右边界进行逆序打印
                    cur = cur.right;
                }
            }
        }
        //最后将整棵树的右边界进行打印
        printRightEdge(head);
    }

    public static void printRightEdge(Node head){
        Node node = reverseEdge(head);
        Node next = node;
        while(next != null){
            System.out.println(next);
            next = next.right;
        }
        reverseEdge(node);
    }

    public static Node reverseEdge(Node head){
        Node pre = null;
        Node cur = head;
        while(cur != null){
            Node next = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    //通过morris遍历完成对搜索二叉树的判断
    public static boolean isBST(Node head){
        Node cur = head;
        Node mostRight;
        boolean isBST = true;
        while(cur != null){
            if(cur.left != null) {
                mostRight = cur.left;
                while(mostRight.right != null && mostRight.right != cur)
                    mostRight = mostRight.right;
                if(mostRight.right == null){
                    mostRight.right = cur;
                    if(cur.value < cur.left.value)
                        isBST = false;
                    cur = cur.left;
                    continue;
                }else
                    mostRight.right = null;
            }
            if(cur.right != null && cur.value > cur.right.value)
                isBST = false;
            cur = cur.right;
        }
        return isBST;
    }

    //递归的方法
    public static boolean isBST2(Node head){
        boolean[] isBST = {true};
        int[] i = new int[]{Integer.MIN_VALUE};
        process(head, isBST, i);
        return isBST[0];
    }

    public static void process(Node head, boolean[] a, int[] i){
        if(head == null)
            return;
        //只用到了左子树的信息
        process(head.left, a, i);
        if(i[0] != Integer.MIN_VALUE){
            if(i[0] > head.value)
                a[0] = false;
        }
        i[0] = head.value;
        //右子树返回回来并没有使用它的信息
        process(head.right, a, i);
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.right.left = new Node(5);
        head.right.right = new Node(7);
//        morris(head);
//        morrisPre(head);
//        morrisIn(head);
        System.out.println(isBST(head));
//        morrisPos(head);
        //4212346567
    }
}
